#ifndef STRUCTS_H
#define STRUCTS_H
#include <stdlib.h>
#include <limits.h>

/*http://cslibrary.stanford.edu/110/BinaryTrees.html*/

typedef struct nodo{
  /** Struct representando as 'folhas' da
   ** arvore binaria.Os itens de menor valor
   ** ficam a esquerda,e os de maior valor
   ** ficam a direita.
   **/
  int valor;
  struct nodo *esquerda,
              *direita;
}No;

/*Funcoes referentes a struct nodo ( AKA No)*/

No* novo_no(int valor){
  /* inicializa nova folha */
  No* nova_folha = (No*) malloc(sizeof(No));
  nova_folha->valor = valor;
  nova_folha->esquerda = NULL;
  nova_folha->direita = NULL;
  return nova_folha;
}

void adiciona_elemento(int valor,No** folha){
  /* Utilizando ponteiros para ponteiros
   * para poder usar essa funcao para criar uma
   * arvore nova,inicializando o ponteiro raiz
   */
  if(*folha == NULL){
    *folha = novo_no(valor);
  }
  else if(valor > (*folha)->valor){
    adiciona_elemento(valor,&(*folha)->direita);
  }
  else if(valor < (*folha)->valor){
    adiciona_elemento(valor,&(*folha)->esquerda);
  }
}

void remove_elemento(No *folha){
  /* Remove todos os elementos abaixo de folha */
  if(folha != NULL){
    remove_elemento(folha->esquerda);
    remove_elemento(folha->direita);
    free(folha);
  }
}

No* busca(int valor,No* folha){
  /* Busca elemento pelo valor
   * retorna NULL caso nao encontre
   */
  if(folha != NULL){
    if(folha->valor == valor)
      return folha;
    else if(folha->valor < valor)
      return busca(valor,folha->esquerda);
    else
      return busca(valor,folha->direita);
  }
  return NULL;
}

int tamanho(No *folha){
  /* retorna o numero de nos na arvore*/
  if(folha != NULL){
    return 1+tamanho(folha->esquerda)+tamanho(folha->direita);
  }
  return 0;
}

int profundidade(No* folha){
  /* retorna a profundidade do maior caminho a partir de folha*/
  if(folha != NULL){
    int esq = profundidade(folha->esquerda);
    int dir = profundidade(folha->direita);

    if(esq == dir || esq > dir)
      return 1+esq;
    else
      return 1+dir;
  }
  return 0;
}

int minimo(No *folha){
  /* retorna o menor valor guardado numa arvore
   * nao vazia.
   */
  if(folha != NULL){
    int ret = minimo(folha->esquerda);
    return (ret < folha->valor) ? ret : folha->valor;
  }
  return INT_MAX;
}

int maximo(No *folha){
  /* retorna o maior valor guardado numa arvore
   * nao vazia.
   */
  if(folha != NULL){
    int ret = maximo(folha->direita);
    return (ret > folha->valor) ? ret : folha->valor;
  }
  return INT_MIN;
}

void imprime_arvore(No* folha){
  /* imprime a arvore em ordem crescente de valores*/
  if(folha != NULL){
    imprime_arvore(folha->esquerda);
    printf("%d ",folha->valor);
    imprime_arvore(folha->direita);
  }
}

#endif // STRUCTS_H
